package com.gitee.wsl.collections.deque

import com.gitee.wsl.ext.array.contentHashCode
import com.gitee.wsl.ext.base.Arrays
import com.gitee.wsl.ext.bitcode.umod
import com.gitee.wsl.ext.map.toLinkedMap

/**
 * Deque structure supporting constant time of appending/removing from the start or the end of the list
 * when there is room in the underlying array.
 */

open class LongDeque(initialCapacity: Int) : MutableCollection<Long> {
    private var _start: Int = 0
    private var _size: Int = 0
    private var data: LongArray = LongArray(initialCapacity) as LongArray
    private val _data: LongArray get() = data.fastCastTo()
    private val capacity: Int get() = data.size

    constructor() : this(initialCapacity = 16)

    override val size: Int get() = _size

    override fun isEmpty(): Boolean = size == 0

    private fun resizeIfRequiredFor(count: Int) {
        if (size + count > capacity) {
            val i = this.data
            val istart = this._start
            val _o = LongArray(maxOf(this.data.size + 7, maxOf(size + count, this.data.size * 2)))
            val o = _o as LongArray
            copyCyclic(i, istart, o, this._size)
            this.data = o
            this._start = 0
        }
    }

    private fun copyCyclic(i: LongArray, istart: Int, o: LongArray, count: Int) {
        val size1 = kotlin.math.min(i.size - istart, count)
        val size2 = count - size1
        Arrays.arraycopy(i, istart, o, 0, size1)
        if (size2 > 0) Arrays.arraycopy(i, 0, o, size1, size2)
    }

    fun addLast(item: Long) {
        resizeIfRequiredFor(1)
        _addLast(item)
    }

    fun addFirst(item: Long) {
        resizeIfRequiredFor(1)
        _start = (_start - 1) umod capacity
        _size++
        data[_start] = item
    }

    fun addAll(array: LongArray): Boolean = _addAll(array.size) { array[it] }
    fun addAll(list: List<Long>): Boolean = _addAll(list.size) { list[it] }
    fun addAll(items: Iterable<Long>): Boolean = addAll(items.toList())
    override fun addAll(elements: Collection<Long>): Boolean = addAll(elements.toList())

    fun addAllFirst(items: LongArray): Boolean = _addAllFirst(items.size) { items[it] }
    fun addAllFirst(items: List<Long>): Boolean = _addAllFirst(items.size) { items[it] }
    fun addAllFirst(items: Iterable<Long>): Boolean = addAllFirst(items.toList())
    fun addAllFirst(items: Collection<Long>): Boolean = addAllFirst(items.toList())

    private inline fun _addAll(count: Int, block: (Int) -> Long): Boolean {
        resizeIfRequiredFor(count)
        val base = _start + _size
        for (n in 0 until count) data[(base + n) % capacity] = block(n)
        _size += count
        return true
    }

    private inline fun _addAllFirst(count: Int, block: (Int) -> Long): Boolean {
        resizeIfRequiredFor(count)
        _start = (_start - count) umod capacity
        _size += count
        var pos = _start
        for (n in 0 until count) data[pos++ umod capacity] = block(n)
        return true
    }

    private fun _addLast(item: Long) {
        data[(_start + _size) % capacity] = item
        _size++
    }

    private fun nullify(index: Int) {
        _data[index] = 0L // Prevent leaks
    }

    fun removeFirst(): Long {
        if (_size <= 0) throw IndexOutOfBoundsException()
        val out = first
        nullify(_start)
        _start = (_start + 1) % capacity;
        _size--
        return out
    }

    fun removeLast(): Long {
        if (_size <= 0) throw IndexOutOfBoundsException()
        val out = last
        nullify(internalIndex(size - 1))
        _size--
        return out
    }

    fun removeAt(index: Int): Long {
        if (index < 0 || index >= size) throw IndexOutOfBoundsException()
        if (index == 0) return removeFirst()
        if (index == size - 1) return removeLast()

        // @TODO: We could use two arraycopy per branch to prevent umodding twice per element.
        val old = this[index]
        if (index < size / 2) {
            for (n in index downTo 1) this[n] = this[n - 1]
            _start = (_start + 1) umod capacity
        } else {
            for (n in index until size - 1) this[n] = this[n + 1]
        }

        _size--
        return old
    }

    override fun add(element: Long): Boolean = true.apply { addLast(element) }
    override fun clear() { _size = 0 }
    override fun remove(element: Long): Boolean {
        val index = indexOf(element)
        if (index >= 0) removeAt(index)
        return (index >= 0)
    }

    override fun removeAll(elements: Collection<Long>): Boolean = _removeRetainAll(elements, retain = false)
    override fun retainAll(elements: Collection<Long>): Boolean = _removeRetainAll(elements, retain = true)

    private fun _removeRetainAll(elements: Collection<Long>, retain: Boolean): Boolean {
        val eset = elements.toSet()
        val _temp = this.data.copyOf()
        var tsize = 0
        val osize = size
        for (n in 0 until size) {
            val c = this[n]
            if ((c in eset) == retain) {
                _temp[tsize++] = c
            }
        }
        this.data = _temp
        this._start = 0
        this._size = tsize
        return tsize != osize
    }

    val first: Long get() = data[_start]
    val last: Long get() = data[internalIndex(size - 1)]

    private fun internalIndex(index: Int) = (_start + index) umod capacity

    operator fun set(index: Int, value: Long) { data[internalIndex(index)] = value }
    operator fun get(index: Int): Long = data[internalIndex(index)]

    fun getOrNull(index: Int): Long? = if (index in indices) get(index) else null

    override fun contains(element: Long): Boolean = (0 until size).any { this[it] == element }

    fun indexOf(element: Long): Int {
        for (n in 0 until size) if (this[n] == element) return n
        return -1
    }

    override fun containsAll(elements: Collection<Long>): Boolean {
        val emap = elements.map { it to 0 }.toLinkedMap()
        for (it in 0 until size) {
            val e = this[it]
            if (e in emap) emap[e] = 1
        }
        return emap.values.all { it == 1 }
    }

    override fun iterator(): MutableIterator<Long> {
        val that = this
        return object : MutableIterator<Long> {
            var index = 0
            override fun next(): Long = that[index++]
            override fun hasNext(): Boolean = index < size
            override fun remove() { removeAt(--index) }
        }
    }

    override fun hashCode(): Int = contentHashCode(size) { this[it] }

    override fun equals(other: Any?): Boolean {
        if (other !is LongDeque) return false
        if (other.size != this.size) return false
        for (n in 0 until size) if (this[n] != other[n]) return false
        return true
    }

    override fun toString(): String {
        val sb = StringBuilder()
        sb.append('[')
        for (n in 0 until size) {
            sb.append(this[n])
            if (n != size - 1) sb.append(", ")
        }
        sb.append(']')
        return sb.toString()
    }
}